package vip.zhenzicheng.algorithm.leetcode.array;

import vip.zhenzicheng.algorithm.util.ArrayUtils;

/**
 * <a href="https://leetcode.cn/problems/next-permutation/">下一个排列 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-16 19:08
 */
public class NextPermutation_31 {

  public static void main(String[] args) {
    NextPermutation_31 test = new NextPermutation_31();
    int[] nums = new int[]{3, 1, 2};
    test.nextPermutation(nums);

    ArrayUtils.printArray(nums);
  }

  public void nextPermutation(int[] nums) {
    if (nums.length < 2) {
      return;
    }

    int small = nums.length - 2;
    while (small >= 0 && nums[small] >= nums[small + 1]) { // 倒数找到一个较小数
      small--;
    }
    if (small >= 0) {
      int max = nums.length - 1;
      while (max >= 0 && nums[small] >= nums[max]) { // 找到尽可能小的较大数
        max--;
      }
      // 退出退出循环说明找到了尽可能小的大数 nums[max] > nums[small]
      // 交换最大最小
      swap(nums, small, max);
    }
    // 反转
    reverse(nums, small + 1); // 交换以后从下一位开始必定是降序排序，为了保持排列最小所以需要升序排列
  }

  public void reverse(int[] arr, int start) {
    int end = arr.length - 1;
    while (start < end) {
      swap(arr, start, end);
      start++;
      end--;
    }
  }

  // 交换
  public void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}
